home *** CD-ROM | disk | FTP | other *** search
/ Nebula 2 / Nebula Two.iso / SourceCode / MiscKit1.7.1 / MiscKit / Palettes / MiscTableScroll / MiscTableScrollSort.M < prev    next >
Encoding:
Text File  |  1996-02-11  |  28.0 KB  |  954 lines
  1. //=============================================================================
  2. //
  3. //        Copyright (C) 1995, 1996 by Paul S. McCarthy and Eric Sunshine.
  4. //                Written by Paul S. McCarthy and Eric Sunshine.
  5. //                            All Rights Reserved.
  6. //
  7. //        This notice may not be removed from this source code.
  8. //
  9. //        This object is included in the MiscKit by permission from the authors
  10. //        and its use is governed by the MiscKit license, found in the file
  11. //        "License.rtf" in the MiscKit distribution.    Please refer to that file
  12. //        for a list of all applicable permissions and restrictions.
  13. //
  14. //=============================================================================
  15. //-----------------------------------------------------------------------------
  16. // MiscTableScrollSort.M
  17. //
  18. //        Sorting support for MiscTableScroll.
  19. //
  20. // FIXME: OPTIMIZATION -- Don't make a function call to do the comparisons
  21. //        unless the user has installed a custom sort function.  Use a big
  22. //        switch statement.  (This eliminates one function call per comparison.)
  23. //
  24. // FIXME: OPTIMIZATION -- Pre-compute the method that will be used to access
  25. //        the values in each slot.  We should not need to keep testing whether
  26. //        or not the delegate / dataDelegate -respondTo: tableScroll:intValueAt::
  27. //        for instance.  Figure this stuff out ahead of time, and store the
  28. //        information in the MiscSlotSortInfo structure somewhere.  (This can
  29. //        eliminate somewhere around 4-6 function calls per comparison.)
  30. // 
  31. // FIXME: OPTIMIZATION -- Consider re-using the sort info objects at least to 
  32. //        avoid allocating and freeing entry_info[] and buff[] all the time.    
  33. //        Consider embedding one of them right in the table-scroll itself.
  34. //-----------------------------------------------------------------------------
  35. //-----------------------------------------------------------------------------
  36. // $Id: MiscTableScrollSort.M,v 1.2 96/02/12 00:06:06 sunshine Exp $
  37. // $Log:        MiscTableScrollSort.M,v $
  38. // Revision 1.2     96/02/12  00:06:06     sunshine
  39. // Fixed bug where -border:setSlot:sortType: was ignoring case-sensitive
  40. // title, case-insensitive title, state, and unsigned state sort types.     This
  41. // resulted in the default -stringValue variation to be used for those slots,
  42. // which is clearly incorrect.
  43. // 
  44. // Revision 1.1     96/01/13  23:31:59     zarnuk
  45. // Split-off from MiscTableScroll to ease maintenance.
  46. // Now pre-computes more sorting information.
  47. // Now has builtin median-of-three quick sort function.
  48. // (Much closer to being re-entrant and thread-safe now).
  49. // Now uses cell coordinates instead of cell-pointers for cell-wise compare.
  50. // Now handles single-buffered lazy tables.     (bug fix).
  51. // Now uses ...ValueAt:: methods to enhance performance of lazy tables.
  52. // Added new methods: -slotsAreSorted:, -border:slotIsSorted:,
  53. //       -border:compareSlots::
  54. //-----------------------------------------------------------------------------
  55. #import <misckit/MiscTableScroll.h>
  56. #import "MiscTableBorder.h"
  57.  
  58. extern "C" {
  59. #import <assert.h>
  60. #import <stdlib.h>
  61. #import <strings.h>
  62. }
  63.  
  64. //=============================================================================
  65. // CELL-VALUE ACCESS
  66. //=============================================================================
  67.  
  68. //-----------------------------------------------------------------------------
  69. // copy_string
  70. //-----------------------------------------------------------------------------
  71. static char* copy_string( char const* s, MiscSlotSortInfo* info )
  72.     {
  73.     int len = strlen( s ) + 1;
  74.     int sz = info->buff_size;
  75.     char* t = info->buff;
  76.     if (sz < len)
  77.         {
  78.         do { sz += 256; } while (sz < len);
  79.         NXZone* const z = info->zone;
  80.         if (t == 0)
  81.             t = (char*) NXZoneMalloc( z, sz );
  82.         else
  83.             t = (char*) NXZoneRealloc( z, t, sz );
  84.         info->buff_size = sz;
  85.         info->buff = t;
  86.         }
  87.     memcpy( t, s, len );
  88.     return t;
  89.     }
  90.  
  91.  
  92. //-----------------------------------------------------------------------------
  93. // cell_str
  94. //-----------------------------------------------------------------------------
  95. static inline char const* cell_str( int r, int c,
  96.                 MiscSlotSortInfo* info, BOOL make_copy )
  97.     {
  98.     char const* t = [info->table_scroll stringValueAt:r:c];
  99.     if (t == 0)
  100.         t = "";
  101.     else if (make_copy)
  102.         t = copy_string( t, info );
  103.     return t;
  104.     }
  105.  
  106.  
  107. //-----------------------------------------------------------------------------
  108. // cell_title
  109. //-----------------------------------------------------------------------------
  110. static inline char const* cell_title( int r, int c,
  111.                 MiscSlotSortInfo* info, BOOL make_copy )
  112.     {
  113.     char const* t = [info->table_scroll titleAt:r:c];
  114.     if (t == 0)
  115.         t = "";
  116.     else if (make_copy)
  117.         t = copy_string( t, info );
  118.     return t;
  119.     }
  120.  
  121.  
  122. //-----------------------------------------------------------------------------
  123. // cell_int
  124. //-----------------------------------------------------------------------------
  125. static inline int cell_int( int r, int c, MiscSlotSortInfo const* info )
  126.     {
  127.     return ([info->table_scroll intValueAt:r:c]);
  128.     }
  129.  
  130.  
  131. //-----------------------------------------------------------------------------
  132. // cell_state
  133. //-----------------------------------------------------------------------------
  134. static inline int cell_state( int r, int c, MiscSlotSortInfo const* info )
  135.     {
  136.     return ([info->table_scroll stateAt:r:c]);
  137.     }
  138.  
  139.  
  140. //-----------------------------------------------------------------------------
  141. // cell_tag
  142. //-----------------------------------------------------------------------------
  143. static inline int cell_tag( int r, int c, MiscSlotSortInfo const* info )
  144.     {
  145.     return ([info->table_scroll tagAt:r:c]);
  146.     }
  147.  
  148.  
  149. //-----------------------------------------------------------------------------
  150. // cell_float
  151. //-----------------------------------------------------------------------------
  152. static inline float cell_float( int r, int c, MiscSlotSortInfo const* info )
  153.     {
  154.     return ([info->table_scroll floatValueAt:r:c]);
  155.     }
  156.  
  157.  
  158. //-----------------------------------------------------------------------------
  159. // cell_double
  160. //-----------------------------------------------------------------------------
  161. static inline double cell_double( int r, int c, MiscSlotSortInfo const* info )
  162.     {
  163.     return ([info->table_scroll doubleValueAt:r:c]);
  164.     }
  165.  
  166.  
  167. //=============================================================================
  168. // CELL COMPARISON FUNCTIONS
  169. //=============================================================================
  170.  
  171. //-----------------------------------------------------------------------------
  172. // cmp_ititle
  173. //-----------------------------------------------------------------------------
  174. static int cmp_ititle( int r1, int c1, int r2, int c2,
  175.                         MiscSlotSortInfo* info )
  176.     {
  177.     char const* const s1 = cell_title( r1,c1,info,info->need_copy );
  178.     char const* const s2 = cell_title( r2,c2,info,NO );
  179.     // FIXME: Use NXOrderStrings() here.
  180.     return strcasecmp( s1, s2 );
  181.     }
  182.  
  183.  
  184. //-----------------------------------------------------------------------------
  185. // cmp_title
  186. //-----------------------------------------------------------------------------
  187. static int cmp_title( int r1, int c1, int r2, int c2,
  188.                         MiscSlotSortInfo* info )
  189.     {
  190.     char const* const s1 = cell_title( r1,c1,info,info->need_copy );
  191.     char const* const s2 = cell_title( r2,c2,info,NO );
  192.     return strcmp( s1, s2 );
  193.     }
  194.  
  195.  
  196. //-----------------------------------------------------------------------------
  197. // cmp_state
  198. //-----------------------------------------------------------------------------
  199. static int cmp_state( int r1, int c1, int r2, int c2,
  200.                         MiscSlotSortInfo const* info )
  201.     {
  202.     int const x1 = cell_state(r1,c1,info);
  203.     int const x2 = cell_state(r2,c2,info);
  204.     if (x1 < x2)
  205.         return -1;
  206.     if (x1 > x2)
  207.         return 1;
  208.     return 0;
  209.     }
  210.  
  211.  
  212. //-----------------------------------------------------------------------------
  213. // cmp_ustate
  214. //-----------------------------------------------------------------------------
  215. static int cmp_ustate( int r1, int c1, int r2, int c2,
  216.                         MiscSlotSortInfo const* info )
  217.     {
  218.     unsigned int const x1 = (unsigned int) cell_state(r1,c1,info);
  219.     unsigned int const x2 = (unsigned int) cell_state(r2,c2,info);
  220.     if (x1 < x2)
  221.         return -1;
  222.     if (x1 > x2)
  223.         return 1;
  224.     return 0;
  225.     }
  226.  
  227.  
  228. //-----------------------------------------------------------------------------
  229. // cmp_istr
  230. //-----------------------------------------------------------------------------
  231. static int cmp_istr( int r1, int c1, int r2, int c2,
  232.                         MiscSlotSortInfo* info )
  233.     {
  234.     char const* const s1 = cell_str( r1,c1,info,info->need_copy );
  235.     char const* const s2 = cell_str( r2,c2,info,NO );
  236.     // FIXME: Use NXOrderStrings() here.
  237.     return strcasecmp( s1, s2 );
  238.     }
  239.  
  240.  
  241. //-----------------------------------------------------------------------------
  242. // cmp_str
  243. //-----------------------------------------------------------------------------
  244. static int cmp_str( int r1, int c1, int r2, int c2,
  245.                         MiscSlotSortInfo* info )
  246.     {
  247.     char const* const s1 = cell_str( r1,c1,info,info->need_copy );
  248.     char const* const s2 = cell_str( r2,c2,info,NO );
  249.     return strcmp( s1, s2 );
  250.     }
  251.  
  252.  
  253. //-----------------------------------------------------------------------------
  254. // cmp_int
  255. //-----------------------------------------------------------------------------
  256. static int cmp_int( int r1, int c1, int r2, int c2,
  257.                         MiscSlotSortInfo const* info )
  258.     {
  259.     int const x1 = cell_int(r1,c1,info);
  260.     int const x2 = cell_int(r2,c2,info);
  261.     if (x1 < x2)
  262.         return -1;
  263.     if (x1 > x2)
  264.         return 1;
  265.     return 0;
  266.     }
  267.  
  268.  
  269. //-----------------------------------------------------------------------------
  270. // cmp_uint
  271. //-----------------------------------------------------------------------------
  272. static int cmp_uint( int r1, int c1, int r2, int c2,
  273.                         MiscSlotSortInfo const* info )
  274.     {
  275.     unsigned int const x1 = (unsigned int) cell_int(r1,c1,info);
  276.     unsigned int const x2 = (unsigned int) cell_int(r2,c2,info);
  277.     if (x1 < x2)
  278.         return -1;
  279.     if (x1 > x2)
  280.         return 1;
  281.     return 0;
  282.     }
  283.  
  284.  
  285. //-----------------------------------------------------------------------------
  286. // cmp_tag
  287. //-----------------------------------------------------------------------------
  288. static int cmp_tag( int r1, int c1, int r2, int c2,
  289.                         MiscSlotSortInfo const* info )
  290.     {
  291.     int const x1 = cell_tag(r1,c1,info);
  292.     int const x2 = cell_tag(r2,c2,info);
  293.     if (x1 < x2)
  294.         return -1;
  295.     if (x1 > x2)
  296.         return 1;
  297.     return 0;
  298.     }
  299.  
  300.  
  301. //-----------------------------------------------------------------------------
  302. // cmp_utag
  303. //-----------------------------------------------------------------------------
  304. static int cmp_utag( int r1, int c1, int r2, int c2,
  305.                         MiscSlotSortInfo const* info )
  306.     {
  307.     unsigned int const x1 = (unsigned int) cell_tag(r1,c1,info);
  308.     unsigned int const x2 = (unsigned int) cell_tag(r2,c2,info);
  309.     if (x1 < x2)
  310.         return -1;
  311.     if (x1 > x2)
  312.         return 1;
  313.     return 0;
  314.     }
  315.  
  316.  
  317. //-----------------------------------------------------------------------------
  318. // cmp_float
  319. //-----------------------------------------------------------------------------
  320. static int cmp_float( int r1, int c1, int r2, int c2,
  321.                         MiscSlotSortInfo const* info )
  322.     {
  323.     float const x1 = cell_float(r1,c1,info);
  324.     float const x2 = cell_float(r2,c2,info);
  325.     if (x1 < x2)
  326.         return -1;
  327.     if (x1 > x2)
  328.         return 1;
  329.     return 0;
  330.     }
  331.  
  332.  
  333. //-----------------------------------------------------------------------------
  334. // cmp_double
  335. //-----------------------------------------------------------------------------
  336. static int cmp_double( int r1, int c1, int r2, int c2,
  337.                         MiscSlotSortInfo const* info )
  338.     {
  339.     double const x1 = cell_double(r1,c1,info);
  340.     double const x2 = cell_double(r2,c2,info);
  341.     if (x1 < x2)
  342.         return -1;
  343.     if (x1 > x2)
  344.         return 1;
  345.     return 0;
  346.     }
  347.  
  348.  
  349. //-----------------------------------------------------------------------------
  350. // cmp_skip
  351. //-----------------------------------------------------------------------------
  352. static int cmp_skip( int,int,int,int,MiscSlotSortInfo const*)
  353.     {
  354.     return 0;
  355.     }
  356.  
  357.  
  358. //-----------------------------------------------------------------------------
  359. // COMPARE_FUNC[]
  360. //-----------------------------------------------------------------------------
  361. static MiscCompareEntryFunc const COMPARE_FUNC[ MISC_SORT_TYPE_MAX + 1 ] =
  362.         {
  363.         cmp_istr,
  364.         cmp_str,
  365.         cmp_int,
  366.         cmp_uint,
  367.         cmp_tag,
  368.         cmp_utag,
  369.         cmp_float,
  370.         cmp_double,
  371.         cmp_skip,
  372.         cmp_ititle,
  373.         cmp_title,
  374.         cmp_state,
  375.         cmp_ustate
  376.         };
  377.  
  378.  
  379. //=============================================================================
  380. // SLOT-COMPARE
  381. //=============================================================================
  382. //-----------------------------------------------------------------------------
  383. // MiscDefaultCompareSlotFunc
  384. //-----------------------------------------------------------------------------
  385. int MiscDefaultCompareSlotFunc(
  386.         int slot1,
  387.         int slot2,
  388.         MiscSlotSortInfo* info )
  389.     {
  390.     int rc = 0;
  391.     MiscEntrySortInfo const* p = info->entry_info;
  392.     MiscEntrySortInfo const* const plim = p + info->num_entries;
  393.  
  394.     if (info->border_type == MISC_COL_BORDER)            // Row-wise compare
  395.         {
  396.         for ( ; p < plim; p++)
  397.             {
  398.             int const col = p->slot;
  399.             if ((rc = (*(p->compare_func))(slot1,col,slot2,col,info)) != 0)
  400.                 return (p->ascending ? rc : -rc);
  401.             }
  402.         }
  403.     else                                                // Col-wise compare
  404.         {
  405.         for ( ; p < plim; p++)
  406.             {
  407.             int const row = p->slot;
  408.             if ((rc = (*(p->compare_func))(row,slot1,row,slot2,info)) != 0)
  409.                 return (p->ascending ? rc : -rc);
  410.             }
  411.         }
  412.  
  413.     return 0;
  414.     }
  415.  
  416.  
  417.  
  418. //=============================================================================
  419. // QSORT
  420. //=============================================================================
  421.  
  422. //-----------------------------------------------------------------------------
  423. // swap
  424. //-----------------------------------------------------------------------------
  425. inline static void swap( int x, int y, int a[] )
  426.     {
  427.     int t = a[x];
  428.     a[x] = a[y];
  429.     a[y] = t;
  430.     }
  431.  
  432.  
  433. //-----------------------------------------------------------------------------
  434. // do_qsort
  435. //-----------------------------------------------------------------------------
  436. static void do_qsort(
  437.         int a[],
  438.         int N,
  439.         MiscCompareSlotFunc f,
  440.         MiscSlotSortInfo* info )
  441.     {
  442.     assert( N > 1 );
  443.  
  444.     int const STACK_MAX = 64;            // log_base_2(ULNG_MAX) * 2
  445.     int stk[ STACK_MAX ];
  446.     int top = 0;
  447.     int left = 0;
  448.     int right = N - 1;                    // WARNING: N == 0
  449.     int i,j,n;                            // minus one is HUGE value.
  450.  
  451.     for (;;)
  452.         {
  453.         while (right > left)
  454.             {
  455.             n = (right - left) + 1;        // right,left bounds are inclusive.
  456.             if (n >= 3)
  457.                 {
  458.                 int mid = (left + right) >> 1;
  459.                 if ((*f)(a[left],a[right],info) > 0) swap(left,right,a);
  460.                 if ((*f)(a[mid], a[right],info) > 0) swap(mid,right,a);
  461.                 if ((*f)(a[left],a[mid],  info) > 0) swap(left,mid,a);
  462.                 if (n == 3) break;
  463.                 right--;
  464.                 swap(mid,right,a);
  465.                 int v = a[right];
  466.                 i = left;
  467.                 j = right;
  468.                 for (;;)
  469.                     {
  470.                     while ((*f)(a[++i],v,info) < 0) /* empty */;
  471.                     while ((*f)(a[--j],v,info) > 0) /* empty */;
  472.                     if (i >= j) break;
  473.                     swap( i, j, a );
  474.                     }
  475.                 swap( i, right, a );
  476.                 right++;
  477.                 if (i - left > right - i)
  478.                     { stk[top++] = left;  stk[top++] = i-1; left = i+1; }
  479.                 else if (right - i > 1)
  480.                     { stk[top++] = i+1; stk[top++] = right; right = i-1; }
  481.                 else
  482.                     break;
  483.                 }
  484.             else // (n < 3)
  485.                 {
  486.                 if (n > 1) // && (n < 3)
  487.                     {
  488.                     if ((*f)(a[left],a[right],info) > 0)
  489.                         swap(left,right,a);
  490.                     }
  491.                 break;
  492.                 }
  493.             }
  494.         if (top == 0) break;
  495.         right = stk[--top];
  496.         left = stk[--top];
  497.         }
  498.     }
  499.  
  500.  
  501. @implementation MiscTableScroll(Sort)
  502.  
  503. //-----------------------------------------------------------------------------
  504. // - compareSlotFunc
  505. //-----------------------------------------------------------------------------
  506. - (MiscCompareSlotFunc) compareSlotFunc
  507.     {
  508.     return sort_slot_func ? sort_slot_func : MiscDefaultCompareSlotFunc;
  509.     }
  510.  
  511.  
  512. //-----------------------------------------------------------------------------
  513. // - setCompareSlotFunc:
  514. //-----------------------------------------------------------------------------
  515. - (void) setCompareSlotFunc: (MiscCompareSlotFunc) f
  516.     {
  517.     sort_slot_func =  (f ? f : MiscDefaultCompareSlotFunc);
  518.     }
  519.  
  520.  
  521. //-----------------------------------------------------------------------------
  522. // - sortInfoInit:border:
  523. //-----------------------------------------------------------------------------
  524. - (void) sortInfoInit:(MiscSlotSortInfo*)ip border:(MiscBorderType)b
  525.     {
  526.     MiscBorderType const ob = MISC_OTHER_BORDER(b);
  527.     MiscTableBorder* const obp = info[ob]->border;
  528.     NXZone* const z = [self zone];
  529.  
  530.     ip->table_scroll    = self;
  531.     ip->zone            = z;
  532.     ip->border_type        = ob;
  533.     ip->num_entries        = 0;
  534.     ip->entry_info        = 0;
  535.     ip->need_copy        = lazy && ([self buffCount] < 2);
  536.     ip->buff            = 0;
  537.     ip->buff_size        = 0;
  538.  
  539.     int M;                                        // Number of "cols".
  540.     int const* v = [self slotSortVector:ob len:&M];
  541.     if (v == 0 || M == 0)
  542.         {
  543.         v = obp->getPMap();
  544.         M = obp->count();
  545.         }
  546.  
  547.     if (M > 0)
  548.         {
  549.         MiscEntrySortInfo* ep = (MiscEntrySortInfo*) 
  550.                                 NXZoneMalloc( z, M * sizeof(*ep) );
  551.  
  552.         if (ep != 0)
  553.             {
  554.             ip->num_entries        = M;
  555.             ip->entry_info        = ep;
  556.  
  557.             int j = 0;
  558.             for (int i = 0; i < M; i++)
  559.                 {
  560.                 MiscEntrySortInfo& r = ep[j++];
  561.                 int n = (v ? v[i] : i);
  562.                 BOOL was_neg = (n < 0);
  563.                 if (was_neg)
  564.                     n = -n;
  565.                 r.slot = n;
  566.                 if ([self border:ob slotSortDirection:n]==MISC_SORT_DESCENDING)
  567.                     was_neg = !was_neg;
  568.                 r.ascending = !was_neg;
  569.                 if ((r.compare_func = [self border:ob slotSortFunc:n]) == 0)
  570.                     {
  571.                     MiscSortType t = [self border:ob slotSortType:n];
  572.                     if ((unsigned int)t <= (unsigned int)MISC_SORT_TYPE_MAX &&
  573.                         t != MISC_SORT_SKIP)
  574.                         {
  575.                         r.sort_type = t;
  576.                         r.compare_func = COMPARE_FUNC[t];
  577.                         }
  578.                     else // No custom function, and sort-type == skip.
  579.                         {
  580.                         j--;    // Do not include this slot.
  581.                         }
  582.                     }
  583.                 else
  584.                     r.sort_type = MISC_SORT_CUSTOM;
  585.                 }
  586.             ip->num_entries = j;        // Number of non-skip slots.
  587.             }
  588.         else
  589.             {
  590.             [self error:"Memory allocation failure.\n"];
  591.             }
  592.         }
  593.     }
  594.  
  595.  
  596. //-----------------------------------------------------------------------------
  597. // - sortInfoDone:
  598. //-----------------------------------------------------------------------------
  599. - (void) sortInfoDone:(MiscSlotSortInfo*)ip
  600.     {
  601.     if (ip->entry_info != 0)
  602.         {                        // Cast off const-ness.
  603.         NXZoneFree( ip->zone, (MiscEntrySortInfo*) ip->entry_info );
  604.         ip->entry_info = 0;
  605.         }
  606.     if (ip->buff != 0)
  607.         {
  608.         free( ip->buff );
  609.         ip->buff = 0;
  610.         ip->buff_size = 0;
  611.         }
  612.     }
  613.  
  614.  
  615. //-----------------------------------------------------------------------------
  616. // - sortSlots:
  617. //-----------------------------------------------------------------------------
  618. - (void) sortSlots:(MiscBorderType) b
  619.     {
  620.     int const N = [self numSlots:b];            // Number of "rows"
  621.  
  622.     if (N > 1)
  623.         {
  624.         MiscSlotSortInfo sort_info;
  625.         [self sortInfoInit:&sort_info border:b];
  626.         if (sort_info.num_entries > 0)
  627.             {
  628.             NXZone* const z = [self zone];
  629.             int* const new_v2p = (int*) NXZoneMalloc( z, N * sizeof(int) );
  630.             if (new_v2p != 0)
  631.                 {
  632.                 for (int j = 0; j < N; j++)
  633.                     new_v2p[j] = j;
  634.     
  635.                 do_qsort( new_v2p, N, [self compareSlotFunc], &sort_info );
  636.  
  637.                 info[b]->border->setPMap( new_v2p );
  638.  
  639.                 [self update];
  640.                 NXZoneFree( z, new_v2p );
  641.                 }
  642.             else
  643.                 {
  644.                 [self error:"Memory allocation failure.\n" ];
  645.                 }
  646.             }
  647.         [self sortInfoDone:&sort_info];
  648.         }
  649.     }
  650.  
  651. - (void) sortCols { [self sortSlots:MISC_COL_BORDER]; }
  652. - (void) sortRows { [self sortSlots:MISC_ROW_BORDER]; }
  653.  
  654.  
  655. //-----------------------------------------------------------------------------
  656. // - border:compareSlots::info:
  657. //-----------------------------------------------------------------------------
  658. - (int) border:(MiscBorderType)b compareSlots:(int)slot1 :(int)slot2
  659.         info:(MiscSlotSortInfo*)ip
  660.     {
  661.     return (*[self compareSlotFunc])( slot1, slot2, ip );
  662.     }
  663.  
  664. - (int) compareCols:(int)c1 :(int)c2 info:(MiscSlotSortInfo*)ip
  665.         { return [self border:MISC_COL_BORDER compareSlots:c1:c2 info:ip]; }
  666. - (int) compareRows:(int)r1 :(int)r2 info:(MiscSlotSortInfo*)ip
  667.         { return [self border:MISC_ROW_BORDER compareSlots:r1:r2 info:ip]; }
  668.  
  669.  
  670. //-----------------------------------------------------------------------------
  671. // - border:compareSlots::
  672. //-----------------------------------------------------------------------------
  673. - (int) border:(MiscBorderType)b compareSlots:(int)slot1 :(int)slot2
  674.     {
  675.     int rc = 0;
  676.     MiscSlotSortInfo sort_info;
  677.     [self sortInfoInit:&sort_info border:b];
  678.     if (sort_info.num_entries > 0)
  679.         rc = [self border:b compareSlots:slot1:slot2 info:&sort_info];
  680.     [self sortInfoDone:&sort_info];
  681.     return rc;
  682.     }
  683.  
  684. - (int) compareCols:(int)c1 :(int)c2
  685.         { return [self border:MISC_COL_BORDER compareSlots:c1:c2]; }
  686. - (int) compareRows:(int)r1 :(int)r2
  687.         { return [self border:MISC_ROW_BORDER compareSlots:r1:r2]; }
  688.  
  689.  
  690. //-----------------------------------------------------------------------------
  691. // - border:sortSlot:
  692. //-----------------------------------------------------------------------------
  693. - (BOOL) border:(MiscBorderType)b sortSlot:(int)pslot
  694.     {
  695.     BOOL moved = NO;
  696.  
  697.     int const N = [self numSlots:b];            // Number of "rows"
  698.  
  699.     if (N > 1)
  700.         {
  701.         MiscSlotSortInfo sort_info;
  702.         [self sortInfoInit:&sort_info border:b];
  703.         if (sort_info.num_entries > 0)
  704.             {
  705.             MiscCompareSlotFunc func = [self compareSlotFunc];
  706.  
  707.             int const vslot = [self border:b slotPosition:pslot];
  708.             int const prev = (vslot > 0 ?
  709.                         [self border:b slotAtPosition:vslot - 1] : -1);
  710.             int const next = (vslot < N - 1 ?
  711.                         [self border:b slotAtPosition:vslot + 1] : N);
  712.     
  713.             int lo = vslot;
  714.             int hi = vslot - 1;
  715.     
  716.             if (prev >= 0 && (*func)( pslot, prev, &sort_info ) < 0)
  717.                 {
  718.                 lo = 0;
  719.                 hi = vslot - 2;
  720.                 }
  721.             else if (next < N && (*func)( pslot, next, &sort_info) > 0)
  722.                 {
  723.                 lo = vslot + 1;
  724.                 hi = N - 1;
  725.                 }
  726.     
  727.             while (lo <= hi)    // Binary search.
  728.                 {
  729.                 int const mid = (lo + hi) >> 1;
  730.                 int const n = [self border:b slotAtPosition:mid];
  731.                 int const cmp = (*func)( pslot, n, &sort_info );
  732.                 if (cmp < 0)
  733.                     hi = mid - 1;
  734.                 else
  735.                     lo = mid + 1;
  736.                 }
  737.     
  738.             if (lo != vslot)
  739.                 {
  740.                 [self border:b moveSlotFrom:vslot to:lo];
  741.                 [self update];
  742.                 moved = YES;
  743.                 }
  744.             }
  745.         [self sortInfoDone:&sort_info];
  746.         }
  747.  
  748.     return moved;
  749.     }
  750.  
  751. - (BOOL) sortCol:(int)n { return [self border:MISC_COL_BORDER sortSlot:n]; }
  752. - (BOOL) sortRow:(int)n { return [self border:MISC_ROW_BORDER sortSlot:n]; }
  753.  
  754.  
  755. //-----------------------------------------------------------------------------
  756. // - slotsAreSorted:
  757. //-----------------------------------------------------------------------------
  758. - (BOOL) slotsAreSorted:(MiscBorderType)b
  759.     {
  760.     BOOL sorted = YES;
  761.     int const N = [self numSlots:b];            // Number of "rows".
  762.  
  763.     if (N > 1)
  764.         {
  765.         MiscSlotSortInfo data;
  766.         [self sortInfoInit:&data border:b];
  767.         if (data.num_entries > 0)
  768.             {
  769.             MiscCompareSlotFunc func = [self compareSlotFunc];
  770.             for (int i = 1; i < N; i++)
  771.                 if ((*func)( i - 1, i, &data ) > 0)
  772.                     {
  773.                     sorted = NO;
  774.                     break;
  775.                     }
  776.             }
  777.         [self sortInfoDone:&data];
  778.         }
  779.  
  780.     return sorted;
  781.     }
  782.  
  783. - (BOOL) colsAreSorted    { return [self slotsAreSorted:MISC_COL_BORDER]; }
  784. - (BOOL) rowsAreSorted    { return [self slotsAreSorted:MISC_ROW_BORDER]; }
  785.  
  786.  
  787. //-----------------------------------------------------------------------------
  788. // - border:slotIsSorted:
  789. //-----------------------------------------------------------------------------
  790. - (BOOL) border:(MiscBorderType)b slotIsSorted:(int)pslot
  791.     {
  792.     BOOL sorted = YES;
  793.     int const N = [self numSlots:b];            // Number of "rows".
  794.  
  795.     if (N > 1)
  796.         {
  797.         MiscSlotSortInfo data;
  798.         [self sortInfoInit:&data border:b];
  799.         if (data.num_entries > 0)
  800.             {
  801.             MiscCompareSlotFunc func = [self compareSlotFunc];
  802.  
  803.             int const vslot = [self border:b slotPosition:pslot];
  804.             int const prev = (vslot > 0 ?
  805.                         [self border:b slotAtPosition:vslot - 1] : -1);
  806.             int const next = (vslot < N - 1 ?
  807.                         [self border:b slotAtPosition:vslot + 1] : N);
  808.  
  809.             if (prev >= 0 && (*func)( prev, pslot, &data ) > 0)
  810.                 sorted = NO;
  811.  
  812.             else if (next < N && (*func)( pslot, next, &data ) > 0)
  813.                 sorted = NO;
  814.             }
  815.         [self sortInfoDone:&data];
  816.         }
  817.  
  818.     return sorted;
  819.     }
  820.  
  821. - (BOOL) colIsSorted:(int)n
  822.         { return [self border:MISC_COL_BORDER slotIsSorted:n]; }
  823. - (BOOL) rowIsSorted:(int)n
  824.         { return [self border:MISC_ROW_BORDER slotIsSorted:n]; }
  825.  
  826.  
  827. //-----------------------------------------------------------------------------
  828. // autoSort
  829. //-----------------------------------------------------------------------------
  830. - (BOOL) autoSortSlots:(MiscBorderType)b
  831.         { return info[b]->autoSort; }
  832. - (void) border:(MiscBorderType)b setAutoSortSlots:(BOOL)flag
  833.         { info[b]->autoSort = flag; }
  834.  
  835. - (BOOL) autoSortCols
  836.         { return [self autoSortSlots:MISC_COL_BORDER]; }
  837. - (void) setAutoSortCols:(BOOL)flag
  838.         { [self border:MISC_COL_BORDER setAutoSortSlots:flag]; }
  839.  
  840. - (BOOL) autoSortRows
  841.         { return [self autoSortSlots:MISC_ROW_BORDER]; }
  842. - (void) setAutoSortRows:(BOOL)flag
  843.         { [self border:MISC_ROW_BORDER setAutoSortSlots:flag]; }
  844.  
  845.  
  846. //-----------------------------------------------------------------------------
  847. // Sort Vector
  848. //-----------------------------------------------------------------------------
  849. - (int const*) slotSortVector:(MiscBorderType)b len:(int*)len
  850.         {
  851.         MiscBorderInfo* const ip = info[b];
  852.         *len = ip->sort_vector_len;
  853.         return ip->sort_vector;
  854.         }
  855.  
  856. - (void) border:(MiscBorderType)b setSlotSortVector:(int const*)v len:(int)n
  857.         {
  858.         NXZone* const z = [self zone];
  859.         MiscBorderInfo* const ip = info[b];
  860.         if (ip->sort_vector != 0)
  861.             NXZoneFree( z, ip->sort_vector );
  862.         if (n > 0)
  863.             {
  864.             int const nbytes = n * sizeof(*v);
  865.             ip->sort_vector_len = n;
  866.             ip->sort_vector = (int*) NXZoneMalloc( z, nbytes );
  867.             memcpy( ip->sort_vector, v, nbytes );
  868.             }
  869.         else
  870.             {
  871.             ip->sort_vector_len = 0;
  872.             ip->sort_vector = 0;
  873.             }
  874.         }
  875.  
  876. - (int const*) colSortVectorLen:(int*)len
  877.         { return [self slotSortVector:MISC_COL_BORDER len:len]; }
  878. - (void) setColSortVector:(int const*)v len:(int)n;
  879.         { [self border:MISC_COL_BORDER setSlotSortVector:v len:n]; }
  880.  
  881. - (int const*) rowSortVectorLen:(int*)len
  882.         { return [self slotSortVector:MISC_ROW_BORDER len:len]; }
  883. - (void) setRowSortVector:(int const*)v len:(int)n;
  884.         { [self border:MISC_ROW_BORDER setSlotSortVector:v len:n]; }
  885.  
  886.  
  887.  
  888. //-----------------------------------------------------------------------------
  889. // Sort Func
  890. //-----------------------------------------------------------------------------
  891. - (MiscCompareEntryFunc) border:(MiscBorderType)b slotSortFunc:(int)n
  892.         { return info[b]->border->getSortFunc_P(n); }
  893. - (void) border:(MiscBorderType)b setSlot:(int)n
  894.                 sortFunc:(MiscCompareEntryFunc)x
  895.         { info[b]->border->setSortFunc_P(n,x); }
  896.  
  897. - (MiscCompareEntryFunc) colSortFunc:(int)n
  898.         { return [self border:MISC_COL_BORDER slotSortFunc:n]; }
  899. - (void) setCol:(int)n sortFunc:(MiscCompareEntryFunc)x
  900.         { [self border:MISC_COL_BORDER setSlot:n sortFunc:x]; }
  901.  
  902. - (MiscCompareEntryFunc) rowSortFunc:(int)n
  903.         { return [self border:MISC_ROW_BORDER slotSortFunc:n]; }
  904. - (void) setRow:(int)n sortFunc:(MiscCompareEntryFunc)x
  905.         { [self border:MISC_ROW_BORDER setSlot:n sortFunc:x]; }
  906.  
  907.  
  908. //-----------------------------------------------------------------------------
  909. // Sort Direction
  910. //-----------------------------------------------------------------------------
  911. - (MiscSortDirection) border:(MiscBorderType)b slotSortDirection:(int)n
  912.         { return info[b]->border->getSortDirection_P(n); }
  913. - (void) border:(MiscBorderType)b setSlot:(int)n
  914.                 sortDirection:(MiscSortDirection)x
  915.         {
  916.         if ((unsigned int) x <= (unsigned int) MISC_SORT_DESCENDING)
  917.             info[b]->border->setSortDirection_P(n,x);
  918.         }
  919.  
  920. - (MiscSortDirection) colSortDirection:(int)n
  921.         { return [self border:MISC_COL_BORDER slotSortDirection:n]; }
  922. - (void) setCol:(int)n sortDirection:(MiscSortDirection)x
  923.         { [self border:MISC_COL_BORDER setSlot:n sortDirection:x]; }
  924.  
  925. - (MiscSortDirection) rowSortDirection:(int)n
  926.         { return [self border:MISC_ROW_BORDER slotSortDirection:n]; }
  927. - (void) setRow:(int)n sortDirection:(MiscSortDirection)x
  928.         { [self border:MISC_ROW_BORDER setSlot:n sortDirection:x]; }
  929.  
  930.  
  931. //-----------------------------------------------------------------------------
  932. // Sort Type
  933. //-----------------------------------------------------------------------------
  934. - (MiscSortType) border:(MiscBorderType)b slotSortType:(int)n;
  935.         { return info[b]->border->getSortType_P(n); }
  936. - (void) border:(MiscBorderType)b setSlot:(int)n
  937.                 sortType:(MiscSortType)x
  938.         {
  939.         if ((unsigned int) x <= (unsigned int) MISC_SORT_TYPE_MAX)
  940.             info[b]->border->setSortType_P(n,x);
  941.         }
  942.  
  943. - (MiscSortType) colSortType:(int)n
  944.         { return [self border:MISC_COL_BORDER slotSortType:n]; }
  945. - (void) setCol:(int)n sortType:(MiscSortType)x
  946.         { [self border:MISC_COL_BORDER setSlot:n sortType:x]; }
  947.  
  948. - (MiscSortType) rowSortType:(int)n
  949.         { return [self border:MISC_ROW_BORDER slotSortType:n]; }
  950. - (void) setRow:(int)n sortType:(MiscSortType)x
  951.         { [self border:MISC_ROW_BORDER setSlot:n sortType:x]; }
  952.  
  953. @end
  954.